package week3;

import base.ListNode;

/**
 *
 * 23. 合并K个升序链表
 * https://leetcode-cn.com/problems/merge-k-sorted-lists/
 *
 *
 * 执行结果： 通过 显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：40.3 MB, 在所有 Java 提交中击败了29.25% 的用户
 * 通过测试用例：133 / 133
 * 炫耀一下:
 */
public class Week3MergeKSortedLists {

    public ListNode mergeTwoLists(ListNode one, ListNode two) {
        if(one == null || two == null) {
            return one != null ? one : two;
        }
        ListNode head = new ListNode(0);
        ListNode tail = head;
        ListNode onePart = one;
        ListNode twoPart = two;
        for(;onePart != null && twoPart != null;) {
            if(onePart.val < twoPart.val) {
                tail.next = onePart;
                onePart = onePart.next;
            } else {
                tail.next = twoPart;
                twoPart = twoPart.next;
            }
            tail = tail.next;
        }
        tail.next = (onePart != null ? onePart : twoPart);
        return head.next;
    }

    public ListNode merge(ListNode[] lists, int left, int right) {
        if(left == right) {
            return lists[left];
        }
        if(left > right) {
            return null;
        }
        int middle = (left + right) >> 1;
        return mergeTwoLists(merge(lists, left, middle), merge(lists, middle + 1, right));
    }

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode result = merge(lists, 0, lists.length - 1);
        return result;
    }




}
